package class3paixu;
import java.util.Arrays;

public class quick {
    public static void main(String[] args) {
        int[] a = {3,6,9,1,4,7,5};
        quickSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }
    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right) {return;}
        int pivot = partition2(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
    private static int partition2(int[] arr, int left, int right) {
        int pivot = arr[left];
        int the_left = left;
        int the_right = right;
        while(the_left != the_right) {
            while(the_left < the_right && arr[the_right] > pivot) {
                the_right--;
            }
            while(the_left < the_right && arr[the_left] <= pivot) {
                the_left++;
            }
            if(the_left < the_right) {
                swap(arr, the_left, the_right);
            }
        }
        arr[left] = arr[the_left];
        arr[the_left] = pivot;
        System.out.println(Arrays.toString(arr));
        return the_left;

    }
    static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
